package sort.impl;

import anaydis.sort.SorterType;
import com.sun.istack.internal.NotNull;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class MergeSortBottomUp extends AbstractSorter {

    public MergeSortBottomUp() {
        super(SorterType.MERGE_BOTTOM_UP);
    }

    public <T> void sort(@NotNull Comparator<T> tComparator, @NotNull List<T> ts) {
        sort(tComparator, ts, 0, ts.size() - 1);          
    }

    private <T> void sort(Comparator<T> tComparator, List<T> ts, int left, int right) {
        if (right <= left) return;
        for (int m = 1; m <= right - left; m = m + m) {
            for (int i = left; i <= right - m ; i += m + m) {
                merge(tComparator, ts, i, i + m - 1, Math.min(i + m + m - 1, right));
            }
        }
    }

    private <T> void merge(Comparator<T> tComparator, List<T> ts, int left, int m, int right) {
        int i, j;
        List<T> aux = new ArrayList<T>();

        for(T t: ts) {
            aux.add(t);
        }
        for (i = m + 1; i > left; i--) {
            aux.set(i - 1, ts.get(i - 1));
        }
        for (j = m; j < right; j++) {
            aux.set(right + m - j, ts.get(j + 1));
        }
        for (int k = left; k <= right; k++) {
            if(j<=i) break;
            if (!greater(tComparator, aux, j, i)) {
                ts.set(k, aux.get(j--));
            } else {
                ts.set(k, aux.get(i++));
            }
        }
    }
}

